package leetcode_core.leetcode_1;

public class SolveSudoku {
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }

    private boolean backtrack(char[][] board,int i,int j){
        int m =9,n=9;
        if(i==m){
            //如果找到一个可行解,那么就触发base-case
            return true;
        }
        if(j==n){
            //如果穷举到最后一列的话就换行就好了
            return backtrack(board,i+1,0);
        }
        //如果该位置是预设的数字,则不需要我们去推导
        if(board[i][j]!='.'){
            return backtrack(board,i,j+1);
        }
        for(char ch = '1';ch<='9';ch++){
            //判定该数字是否合法
            if(!isValid(board,i,j,ch)){
                continue;
            }
            //做选择
            board[i][j] = ch;
            //继续穷举下一个位置
            if(backtrack(board,i,j+1)){
                return true;
            }
            //撤销选择
            board[i][j] = '.';
        }
        return false;
    }
    private boolean isValid(char[][] board,int row,int col,char ch){
        for(int i =0;i<9;i++){
            //判断行是否存在重复
            if(board[row][i] == ch){
                return false;
            }
            //判断列是否存在重复
            if(board[i][col] == ch){
                return false;
            }
            //判断3*3之内是否存在重复
            if(board[(row/3)*3+i/3][(col/3)*3+i%3] == ch){
                return false;
            }
        }
        return true;
    }

}
